package com.chj.leetcode.tijie100to150;

import java.util.ArrayDeque;
import java.util.Deque;

public class Code111_MinimumDepthOfBinaryTree {

//	  Definition for a binary tree node.
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}

	public int minDepth01(TreeNode root) {
		if (root == null) {
			return 0;
		}
		// 左子树的最小深度
		int left = minDepth(root.left);
		// 右子树的最小深度
		int right = minDepth(root.right);
		// 如果left和right都为0，我们返回1即可，
		// 如果left和right只有一个为0，说明他只有一个子结点，我们只需要返回它另一个子节点的最小深度+1即可。
		// 如果left和right都不为0，说明他有两个子节点，我们只需要返回最小深度的+1即可。

		if (left == 0 && right == 0) {
			return 1;
		}

		if (left != 0 && right == 0) {
			return left + 1;
		}

		if (left == 0 && right != 0) {
			return right + 1;
		}

		return Math.min(left, right) + 1;
	}

	public int minDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}

		Deque<TreeNode> queue = new ArrayDeque<>();
		queue.add(root);// 入队
		int level = 0;
		while (!queue.isEmpty()) {// 队列不为空就继续循环
			level++;
			int levelCount = queue.size();
			for (int j = 0; j < levelCount; j++) {
				TreeNode node = queue.poll();// 出队
				// 如果当前node节点的左右子树都为空，直接返回level即可
				if (node.left == null && node.right == null) {
					return level;
				}

				// 左右子节点，哪个不为空，哪个加入到队列中
				if (node.left != null) {
					queue.add(node.left);
				}

				if (node.right != null) {
					queue.add(node.right);
				}
			}
		}
		return -1;
	}

//作者：sdwwld
//链接：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/solution/java-di-gui-he-fei-di-gui-liang-chong-fang-shi-de-/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
